package problem84;

//84.柱状图中最大矩形面积
//https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked

//讲解链接
//https://www.bilibili.com/video/BV1hN4y1V7rV/?spm_id_from=333.337.search-card.all.click&vd_source=05b06c268723949c647a51b2fbacc933

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int weight = i - stack.peek() - 1;
                ret = Math.max(ret, height * weight);
            }
            stack.push(i);
        }

        while (stack.peek() != -1) {
            int height = heights[stack.pop()];
            int weight = n - stack.peek() - 1;
            ret = Math.max(ret, height * weight);
        }
        return ret;
    }
}